package com.tgy.algorithm._经典题目01;

import java.util.Arrays;
import java.util.PriorityQueue;

class LocalInfo {
    int x;
    int y;
    int value;
    LocalInfo(int x,int y,int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }
}

public class _35_两个有序数组中两个数累加和最大的前K个值 {


    public static int[] getMaxK(int[] ones,int[] twos, int k) {

        if (ones == null || ones.length == 0) {
            return null;
        }

        if (twos == null || twos.length == 0) {
            return null;
        }

        int oneLen = ones.length;
        int twoLen = twos.length;

        if ( k >= oneLen * twoLen) {
            k = oneLen * twoLen;
        }

        PriorityQueue<LocalInfo> maxStack = new PriorityQueue<>((l1,l2)->{
            return l2.value - l1.value;
        });

        maxStack.add(new LocalInfo(oneLen - 1,twoLen - 1,ones[oneLen - 1] + twos[twoLen - 1]));
        boolean[][] exits = new boolean[oneLen][twoLen];
        exits[oneLen - 1][twoLen - 1] = true;
        int[] rets = new int[k];
        int retIndex = 0;

        while (retIndex < k) {

            LocalInfo curInfo = maxStack.poll();
            rets[retIndex++] = curInfo.value;

            int leftX = curInfo.x;
            int leftY = curInfo.y;
            if (leftX - 1 >0 && !exits[leftX - 1][leftY]) {
                maxStack.add(new LocalInfo(leftX - 1,leftY,ones[leftX -1] + twos[leftY]));
                exits[leftX - 1][leftY] = true;
            }
            if (leftY - 1 >= 0 && !exits[leftX][leftY - 1]) {
                maxStack.add(new LocalInfo(leftX,leftY - 1,ones[leftX]+twos[leftY - 1]));
                exits[leftX][leftY - 1] = true;
            }
        }

        return rets;
    }

    public static void main(String[] args) {

        /**
         *    2  4  5  7  9
         * 1  3  5  6  8  10
         * 7  9  11 12 14 16
         * 8  10 12 13 15 17
         * 10 12 14 15 17 19
         *
         */

        int[] ones = new int[]{2,4,5,7,9};
        int[] twos = new int[]{1,7,8,10};
        int[] maxK = getMaxK(ones, twos,10);
        System.out.println(Arrays.toString(maxK));
    }
}
